/*
 Given an array S of niitegers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

 Note:
 Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
 The solution set must not contain duplicate triplets.
    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)
*/

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > results;
        // sort the input array
        sort(num.begin(), num.end());
        int start, end, cur = 0;
        while (cur < num.size()) {
            int num_c = num[cur];
            start = cur + 1;
            end = num.size() - 1;
            // Optimization: hit positive number, parsing complete
            if (num_c > 0) return results;
            int target = 0 - num_c;
            // find two numbers with sum to target
            while (start < end) {
                int num_s = num[start];
                int num_e = num[end];
                int sum = num_s + num_e;
                if (sum == target) {
                    vector<int> one_result;
                    // found one, record result
                    one_result.push_back(num_c);
                    one_result.push_back(num_s);
                    one_result.push_back(num_e);
                    results.push_back(one_result);
                    // navigate to next positions
                    while (num[start] == num_s)
                        start++;
                    while (num[end] == num_e)
                        end--;
                } else if (sum < target) {
                    start++;
                } else {
                    end--;
                }
            }
            // advance to the next position
            while (num[cur] == num_c)
                cur++;
        }
        return results;
    }
};
